package leetcode.面试题;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/18 16:26
 * @description :https://leetcode-cn.com/problems/get-kth-magic-number-lcci/
 */
public class 寻找第K大 {
  @Test
  public void test() {
    Solution solution = new Solution();
    System.out.println(solution.findKth(new int[]{4, 7, 2, 1, 3, 5, 6, 9, 8, 10}, 10, 10));
  }

  class Solution {
    public int findKth(int[] nums, int n, int K) {
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjust(nums, i, n);
        }
      System.out.println(Arrays.toString(nums));
        int topK = nums[0];
        for (int i = 0; i < K; i++) {
          topK = nums[0];
            int temp = nums[0];
            nums[0] = nums[n - 1 - i];
            nums[n - 1 - i] = temp;
            adjust(nums, 0, n - 1 - i);
        }
        return topK;
    }

    public void adjust(int[] nums, int parentIndex, int len) {
        int temp = nums[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < len) {
            if (childIndex + 1 < len && nums[childIndex + 1] > nums[childIndex]) {
                childIndex++;
            }
            if (nums[childIndex] <= temp) break;
            nums[parentIndex] = nums[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        nums[parentIndex] = temp;
    }
  }
}
